A Hadamard Transform is obtained by multiplying a Hadamard matrix by a vector. A Hadamard matrix is a square array of positive and negative ones whose rows (and columns) are mutually orthogonal. By mutually orthogonal is meant that the sum of the products of each element of a row (or column) with the corresponding element of another row (or column) is zero. Since the elements of a Hadamard matrix have only two possible values, the orthogonality property requires that half the elements in a row (or column) have the same value as the corresponding elements in any other row (or column) and half have the opposite value. Conversely, the sum of the products of each element of a row (or column) with the same element in the same row (or column) is equal to the number of elements in the row (or column).
The fundamental Hadamard matrix, H2, is a 2×2 array where the subscript of H is the size of the matrix (i.e., the number of its rows and columns). In what is known as normal form, the fundamental Hadamard matrix is written so that its first row and first column contain only positive ones:
                              H          2                =                  [                                                                      +                  1                                                                              +                  1                                                                                                      +                  1                                                                              -                  1                                                              ]                                    (        1        )            Larger Hadamard matrices are generated recursively using the recursion
                              H                      2            n                          =                              H            2                    ⊗                      H                          2                              (                                  n                  -                  1                                )                                                                        (        2        )            where  is a mathematical operator known as the Kronecker product. The Kronecker product multiplies each of the elements of the matrix to the left of the  operator (i.e., the four entries in the fundamental matrix H2) with the matrix H2(n-1) to the right of the  operator. Thus, in equation 2, the Kronecker product replaces each of the four entries in the fundamental matrix H2 with the matrix H2(n-1) multiplied by +1 or −1 depending on the sign of the entry in the fundamental matrix. For example,
                                                                        H                4                            =                                                                    H                    2                                    ⊗                                      H                    2                                                  =                                                      [                                                                                                                        +                            1                                                                                                                                +                            1                                                                                                                                                                            +                            1                                                                                                                                -                            1                                                                                                                ]                                    ⊗                                      [                                                                                                                        +                            1                                                                                                                                +                            1                                                                                                                                                                            +                            1                                                                                                                                -                            1                                                                                                                ]                                                                                                                          =                                                [                                                                                                              +                          1                                                                                                                      +                          1                                                                                                                      +                          1                                                                                                                      +                          1                                                                                                                                                              +                          1                                                                                                                      -                          1                                                                                                                      +                          1                                                                                                                      -                          1                                                                                                                                                              +                          1                                                                                                                      +                          1                                                                                                                      -                          1                                                                                                                      -                          1                                                                                                                                                              +                          1                                                                                                                      -                          1                                                                                                                      -                          1                                                                                                                      +                          1                                                                                                      ]                                =                                  [                                                                                                              H                          2                                                                                                                      H                          2                                                                                                                                                              H                          2                                                                                                                      -                                                      H                            2                                                                                                                                ]                                                                                        (        3        )            Since the only values in the fundamental Hadamard matrix are +1 and −1, the values of any Hadamard matrix can only be +1 or −1. Frequently, other binary expressions are used in place of +1 and −1. For example, a plus sign and a minus sign can be used in place of +1 and −1, respectively; black and white squares can be used instead of +1 and −1 to provide a visual representation of the matrix; and for signaling applications +1 is replaced by a logic 0 and −1 by a logic 1.
The strict binary nature of the Hadamard matrix helps it and related mathematical expressions such as Walsh matrices find wide application in digital communications. A leading example is the CDMA cellular standard, IS-95 which uses a 64×64 Hadamard matrix, H64. The H64 matrix is reproduced at pages 449–450 of J. S. Lee & L. E. Miller, CDMA Systems Engineering Handbook (Artech, 1998).
Different properties of the Hadamard matrix are used in base-to-mobile (forward channel) and mobile-to-base (reverse channel) transmissions in CDMA telephony. The forward channel employs the Hadamard matrix for two purposes. First, each base station uses it to separate outbound transmissions targeted for different mobile users. Second, the base station employs it to spread the signal bandwidth of the transmission.
In the reverse channel, for every six information bits generated at the mobile radio, the mobile radio transmits one 64-bit row of the Hadamard matrix. Each such row is referred to as a Hadamard (or Walsh) sequence. The mobile radio uses the six data bits as a binary address in a lookup-table to select one of the Hadamard matrix rows, and it substitutes the 64 bits of this row for the six data bits. This action both encodes and spreads the signal, as in the forward link, but by a smaller spreading factor, 64/6=10.67.
This encoding acts primarily as a robust error-correction scheme that a mobile radio can perform efficiently and cheaply. When the base station receives the encoded signal, it uses an inverse Hadamard transform to decode the data. Because the data bits are unknown, the base station multiplies a column vector of every 64 received symbols by the entire 64×64 Hadamard matrix, H64. The result is another column vector of 64 values. Mathematically, this operation is represented as the product of the Hadamard matrix H with the input vector x, yielding the Hadamard transform, y:y=H64x  (4)Since the received symbols should be one row of the H64 matrix, they should be orthogonal to all the rows except one of the H64 matrix. Thus, all the rows except one of the resulting column vector should ideally have a zero value and the row that corresponded to the 64 received symbols should be identifiable by the presence of a non-zero value that is the sum of the absolute value of the 64 received symbols. The number of that row, represented in binary, yields the six data bits sent.
Multiplication of two matrices ordinarily requires each element of the first matrix to be multiplied by one of the elements in each column of the second matrix. Thus, when a square matrix of size N is multiplied by a column vector, the number of multiplications ordinarily required is N2.
Certain symmetries of the Hadamard matrix are used in a reorganization of the computation algorithm such that the total number of functions required is reduced to log2(N)*N. An algorithm utilizing this reorganization is referred to as Fast Hadamard Transform (FHT). In prior art implementations of the Hadamard transform, all N inputs of the column vector must be present before the Hadamard transform operation can be performed. Other prior art Hadamard transform implementations use parallel techniques that require storing multiple data samples prior to calculation of the transform. Computer implementations of parallel Hadamard transform engines are thus subject to high memory requirements and latency, and similarly high power consumption.
In view of the foregoing, it is highly desirable to improve the implementation of a Hadamard transform, while reducing the resources used to implement the transform.